#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
const int N=  4e5+10,L = 7e4+10;
int a[N];
int id[N];
int tot;
struct SCT{
    int ls[N];
    int rs[N];
    int siz[N];
    void push_up(int now){
        siz[now] = siz[ls[now]] + siz[rs[now]] + 1;
    }
    int build(const vector<int> &nodes,int l,int r,int il,int ir){
        if(r < l) {
            return 0;
        }
        int mid = (l + r)/2;
        int imid = (il + ir)/2;
        int now = nodes[mid];
        id[now] = imid;
        if(l == r){
            ls[now] = 0;
            rs[now] = 0;
            siz[now] = 1;
            return now;
        }
        ls[now] = build(nodes,l,mid - 1,il,imid - 1);
        rs[now] = build(nodes,mid+1,r,imid + 1,ir);
        push_up(now);
        return now;
    }
    void mark(int now,vector<int> &p){
        if(!now){
            return;
        }
        mark(ls[now],p);
        p.push_back(now);
        mark(rs[now],p);
    }
    const double alpha = 0.75;
    bool insert(int &now,int il,int ir,int rnk,int nid,int sdp){
        int imid = (il + ir)/2;
        if(!now){
            now = nid;
            id[now] = imid;
            siz[now] = 1;
            return sdp > log(tot)/log(alpha);
        }
        bool f;
        if(rnk <= siz[ls[now]]){
            f = insert(ls[now],il,imid - 1,rnk,nid,sdp + 1);
        }else{
            f = insert(rs[now],imid + 1,ir,rnk - siz[ls[now]] - 1,nid,sdp + 1);
        }
        push_up(now);
        if(f && max(siz[ls[now]],siz[rs[now]]) > siz[now]*alpha){
            vector<int> p;
            mark(now,p);
            now = build(p,0,p.size() - 1,il,ir);
            return false;
        }
        return f;
    }
    int kth(int now,int rnk){
        if(rnk == siz[ls[now]] + 1){
            return now;
        }else if(rnk <= siz[ls[now]]){
            return kth(ls[now],rnk);
        }else{
            return kth(rs[now],rnk - siz[ls[now]] - 1);
        }
    }
    void deb(int now){
        if(!now){
            return;
        }
        deb(ls[now]);
        cerr<<a[now]<<' ';
        deb(rs[now]);
    }
}sct;
struct CMP{
    bool operator()(int a,int b) const{
        return id[a] < id[b];
    }
};
struct segment_tree{
    __gnu_pbds::tree<int,__gnu_pbds::null_type,CMP,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update> tre[N<<2];
    void insert(int now,int l,int r,int p,int v){ 
        tre[now].insert(v);
        if(l == r){
            return;
        }
        int mid = (l + r)/2;
        if(p <= mid){
            insert(now<<1,l,mid,p,v);
        }else{
            insert(now<<1|1,mid+1,r,p,v);
        }
    }
    void remove(int now,int l,int r,int p,int v){
        tre[now].erase(v);
        if(l == r){
            return;
        }
        int mid = (l + r)/2;
        if(p <= mid){
            remove(now<<1,l,mid,p,v);
        }else{
            remove(now<<1|1,mid+1,r,p,v);
        }
    }
    int binary(int now,int l,int r,int x,int y,int rnk){
        if(l == r){
            return l;
        }
        int mid = (l + r)/2;
        int lcnt = -tre[now<<1].order_of_key(x);
        auto p = tre[now<<1].upper_bound(y);
        if(p == tre[now<<1].end()){
            lcnt += tre[now<<1].size();
        }else{
            lcnt += tre[now<<1].order_of_key(*p);
        }
        if(lcnt >= rnk){
            return binary(now<<1,l,mid,x,y,rnk);
        }else{
            return binary(now<<1|1,mid+1,r,x,y,rnk - lcnt);
        }
    }
} sg;
int main(){
    int n;
    cin>>n;
    vector<int> inode(n);
    for(int i =1;i<=n;i++){
        cin>>a[i];
        inode[i - 1] = i;
    }
    int rot = sct.build(inode,0,n - 1,1,1e9);
    for(int i = 1;i <= n;i++){
        sg.insert(1,0,L,a[i],i);
    }
    tot = n;
    //sct.deb(rot);
    //cerr<<'\n';
    int q;
    cin>>q;
    int lastans = 0;
    for(int i = 1;i<=q;i++){
        char op;
        cin>>op;
        if(op == 'Q'){
            int x,y,v;
            cin>>x>>y>>v;
            x^=lastans;
            y^=lastans;
            v^=lastans;
            //cerr<<op<<' '<<x<<' '<<y<<' '<<v<<'\n';
            int p1 = sct.kth(rot,x),p2 = sct.kth(rot,y);
            lastans = sg.binary(1,0,L,p1,p2,v);
            cout<<lastans<<'\n';
        }else if(op == 'M'){
            int x,v;
            cin>>x>>v;
            x^=lastans;
            v^=lastans;
            //cerr<<op<<' '<<x<<' '<<v<<'\n';
            int p = sct.kth(rot,x);
            sg.remove(1,0,L,a[p],p);
            a[p] = v;
            sg.insert(1,0,L,a[p],p);
        }else{
            int x,v;
            cin>>x>>v;
            x^=lastans;
            v^=lastans;
            //cerr<<op<<' '<<x<<' '<<v<<'\n';
            a[i + n] = v;
            tot++;
            sct.insert(rot,1,1e9,x - 1,i + n,1);
            sg.insert(1,0,L,a[i + n],i + n);
        }
        //sct.deb(rot);
        //cerr<<'\n';
    }
}